原文題目
You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

題目摘要

1. 題目給予一個 m×n 的二維矩陣，其中每個元素可以是 '0'（代表空）、 '1'（代表新鮮橙子）或 '2'（代表腐爛橙子）
2. 每過一分鐘，與腐爛橙子相鄰的新鮮橙子會變成腐爛橙子。
3. 題目所求：回傳直到沒有新鮮橙子的最短時間，如果這不可能實現則回傳-1。

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

解題思路

1. 設定變數：
   • 設立 m 和 n 來記錄矩陣的行數和列數。
   • 使用 Queue<int[]> 來儲存腐爛橘子的坐標。
   • 使用 freshCount 來記錄網格中新鮮橘子的數量。
   • 使用 minutes 來記錄所需的分鐘數。
2. 遍歷矩陣：
   • 遍歷矩陣中的每個格子，當遇到腐爛橘子（值為 2）時，將其坐標加入 queue。
   • 當遇到新鮮橘子（值為 1）時，增加 freshCount 計數。
   • 如果 freshCount 為 0，則直接返回 0，表示沒有新鮮橘子需要腐爛。
3. 廣度優先搜尋（BFS）：
   • 定義四個方向：下（{1, 0}）、上（{-1, 0}）、右（{0, 1}）、左（{0, -1}）。
   • 循環處理 queue 中的每個腐爛橘子，對其四個相鄰方向進行檢查。
   • 如果相鄰位置是新鮮橘子（值為 1），則將其轉為腐爛橘子（設置為 2），並將新腐爛的橘子坐標加入 queue。
   • 每當處理完一層的橘子後，增加 minutes 計數。
4. 回傳結果：
   • 在完成 BFS 循環後，檢查 freshCount 是否為 0。如果是，返回 minutes，即所需的最少分鐘數。
   • 如果 freshCount 大於 0，表示有新鮮橘子無法腐爛，返回 1。

程式碼

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length; //獲取矩陣列數
        int n = grid[0].length; //獲取矩陣行數
        Queue<int[]> queue = new LinkedList<>(); //設立一個佇列來進行BFS，存儲腐爛橘子的坐標
        int freshCount = 0; //記錄新鮮橘子的數量
        int minutes = 0; //記錄所需的分鐘數
        
        //遍歷矩陣
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //如果是腐爛橘子將其坐標加入佇列
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                } 
                //如果是新鮮橘子增加新鮮橘子的計數
                else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        //如果沒有新鮮橘子則回傳0
        if (freshCount == 0) return 0;        
        
        //如果佇列不為空時就重複執行
        while (!queue.isEmpty()) {
            //定義四個方向的移動量（上下左右），用來遍歷相鄰格子
            int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

            int size = queue.size(); //當前層的橘子數量
            boolean rotted = false; //判斷是否有橘子在這一層腐爛
            
            //處理當前層的所有腐爛橘子
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll(); //取出當前層的腐爛橘子坐標
                int row = curr[0];
                int col = curr[1];
                
                //遍歷四個方向
                for (int[] direction : directions) {
                    int newRow = row + direction[0];
                    int newCol = col + direction[1];
                    
                    //如果新位置在矩陣內並且是新鮮橘子，將其變為腐爛橘子
                    if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2; //將新鮮橘子變為腐爛橘子
                        queue.add(new int[]{newRow, newCol}); //將新腐爛的橘子加入佇列
                        freshCount--; //減少新鮮橘子的數量
                        rotted = true; //記錄這一層有橘子腐爛
                    }
                }
            }
            
            //只要有橘子腐爛就增加分鐘數
            if (rotted) {
                minutes++;
            } 
        }
        //如果所有新鮮橘子都腐爛就回傳分鐘數，否則回傳-1
        return freshCount == 0 ? minutes : -1;
    }
}

結論
我使用廣度優先搜尋（BFS）來解這題題目，首先，用了一個佇列來儲存初始的腐爛橘子的坐標，並設置了一個計數器來追蹤新鮮橘子的數量，接著，通過 BFS 的層次遍歷，每一輪都檢查腐爛橘子的四個相鄰位置，將相鄰的新鮮橘子轉變成腐爛橘子，同時將新腐爛的橘子加入佇列，每當有橘子被腐爛，就會增加分鐘數，但解題過程中要注意如何處理邊界條件，特別是當沒有新鮮橘子或無法完全腐爛的特殊情況。透過這次的練習不僅加深了我對 BFS 在圖形中處理多源傳播問題的理解，也讓我學會了如何有效管理狀態更新和層次遍歷的技巧。